package main.java.utils.hxy.tree;

/**
 * 平衡二叉树
 * 规定 节点 的左子树和右子树的高度 相差大于1 为失衡
 *
 * @param <T>
 */
public class AVLTree<T extends Comparable> {
    private AVLNode<T> root;

    public boolean insert(T data) {
        AVLNode node = new AVLNode (data);
        if (root == null) {
            root = node;
        }
        //找节点
        this.root = insert (node, root);
        return false;
    }

    private AVLNode insert(AVLNode<T> node, AVLNode<T> p) {
        //先判断p是否为空
        if (p == null) {
            p = node;
        }
        //然后进行数值比较
        int result = p.data.compareTo (node.data);
        // P 大于 node
        if (result > 0) {
            //向其左子树插入节点
            p.left = insert (node, p.left);
            //p的平衡性
            if (height (p.left) - height (p.right) > 1) {
                //判断data是插入点的左孩子还是右孩子
                //插入在左孩子的左孩子
                if (node.data.compareTo (p.left.data) < 0) {
                    p = singleRotateLeft (p);
                } else {
                    //插入在左孩子的👉右孩子
                    p = doubleRotateLeft (p);
                }
            }

        }
        // p 小于 node
        else if (result < 0) {
            p.right = insert (node, p.right);
            if (height (p.right) - height (p.left) > 1) {
                //判断data是插入点的左孩子还是右孩子
                //
                if (node.data.compareTo (p.right.data) < 0) {
                    p = singleRotateRight (p);
                } else {
                    //
                    p = doubleRotateRight (p);
                }
            }
        }
        // p == node

        //更新高度
        p.height = Math.max (height (p.left), height (p.right)) + 1;

        return p;
    }

    /**
     * 先进行左旋转 在进行右旋转
     * 左右旋转(LR旋转) x(根) w y 结点 把y变成根结点
     *
     * @param p
     * @return
     */
    private AVLNode<T> doubleRotateLeft(AVLNode<T> p) {
        p.left = singleRotateRight (p.left);
        return singleRotateLeft (p);
    }

    /**
     * 先进行右旋转 在进行左旋转
     * 左右旋转(RR旋转) x(根) w y 结点 把x变成根结点
     *
     * @param p
     * @return
     */
    private AVLNode<T> doubleRotateRight(AVLNode<T> p) {
        p.right = singleRotateLeft (p.right);
        return singleRotateRight (p);
    }

    /**
     * 右旋转
     * p的左子节点 变为p的父节点
     *
     * @param p
     * @return
     */
    private AVLNode<T> singleRotateLeft(AVLNode<T> p) {
        AVLNode<T> left = p.left;
        p.left = left.right;
        left.right = p;
        //更新高度
        p.height = Math.max (height (p.left), height (p.right)) + 1;
        left.height = Math.max (height (left.left), height (left.right)) + 1;
        return left;
    }

    /**
     * 左旋转
     * p的右子节点 变为p的父节点
     *
     * @param p
     * @return
     */
    private AVLNode<T> singleRotateRight(AVLNode<T> p) {
        AVLNode<T> right = p.right;
        p.right = right.left;
        right.left = p;
        //更新高度
        p.height = Math.max (height (p.left), height (p.right)) + 1;
        right.height = Math.max (height (right.left), height (right.right)) + 1;
        return right;
    }

    public Node find(int key) {
        return null;
    }


    public boolean delete(int key) {
        return false;
    }


    public Node findMax() {

        return null;
    }


    public AVLNode<T> findMin(AVLNode p) {
        if (p == null) {
            return null;
        }
        if (p.left == null) {
            return p;
        }
        return findMin (p.left);
    }


    public void infixOrder(Node current) {

    }


    public void preOrder(Node current) {

    }


    public void postOrder(Node current) {

    }


    public boolean isEmpty() {
        return root == null;
    }


    public int size() {
        return 0;
    }


    public int height() {
        return 0;
    }

    /**
     * @param p
     * @return
     */
    public int height(AVLNode<T> p) {
        return p == null ? -1 : p.height;
    }

    public static void main(String[] args) {
        AVLTree<Integer> avlTree = new AVLTree<> ();
        avlTree.insert (10);
        avlTree.insert (11);
        avlTree.insert (8);
        avlTree.insert (9);
        avlTree.insert (6);
        avlTree.insert (7);

        avlTree.printTree (avlTree.root);
    }

    private void printTree(AVLNode<T> t) {
        if (t != null) {
            printTree (t.left);
            System.out.println (t.data);
            printTree (t.right);
        }
    }

    /**
     * 删除方法
     *
     * @param data
     */
    public void remove(T data) {
        if (data == null) {
            throw new RuntimeException ("data can\'t not be null ");
        }
        this.root = remove (data, root);
    }

    /**
     * 1.先找到删除节点
     * 2，删除 进行平衡
     *
     * @param data
     * @param p
     * @return
     */
    private AVLNode<T> remove(T data, AVLNode<T> p) {
        if (p == null) {
            return null;
        }
        int result = p.data.compareTo (data);
        /**
         *  data 在p的左边
         */
        if (result > 0) {
            p.left = remove (data, p.left);
            //更新平衡
            //检测是否平衡
            if(height(p.right)-height(p.left)==2){
                AVLNode<T> currentNode=p.right;
                //判断需要那种旋转
                if(height(currentNode.left)>height(currentNode.right)){
                    //RL
                    p=doubleRotateRight(p);
                }else{
                    //RR
                    p=singleRotateRight(p);
                }
            }
        } else if (result < 0) {
            //data 在p的右边
            p.right = remove (data, p.right);
            //检测是否平衡
            if(height(p.left)-height(p.right)==2){
                AVLNode<T> currentNode=p.left;
                //判断需要那种旋转
                if(height(currentNode.left)<height(currentNode.right)){
                    //RL
                    p=doubleRotateLeft(p);
                }else{
                    //RR
                    p=singleRotateLeft(p);
                }
            }
        } else if (p.left != null && p.right != null) {
            p.data = findMin (p.right).data;
            p.right = remove (p.data, p.right);
        } else {
            //更新p节点
            p = p.left != null ? p.left : p.right;
        }
        if (p != null) {
            p.height = Math.max (height (p.left), height (p.right)) + 1;
        }
        return p;
    }

}

class AVLNode<T extends Comparable> {
    public AVLNode<T> left;//左结点

    public AVLNode<T> right;//右结点

    public T data;

    public int height;//当前结点的高度

    public AVLNode(T data) {
        this (null, null, data);
    }

    public AVLNode(AVLNode<T> left, AVLNode<T> right, T data) {
        this (left, right, data, 0);
    }

    public AVLNode(AVLNode<T> left, AVLNode<T> right, T data, int height) {
        this.left = left;
        this.right = right;
        this.data = data;
        this.height = height;
    }
}